#include "LinkTree.h"



void TreeNode::Connect(TreeNode *parent)
{
    if(!parent)
        return;

    this->parent = parent;
    this->nextSbling = parent->FirstChild;
    parent->FirstChild = this;
}


void TreeNode::DisConnect(TreeNode *parent)
{
    if(parent == nullptr || this->parent != parent)
        return;
    TreeNode * TravalPoint = parent->FirstChild;
    if(this == parent->FirstChild)
        parent->FirstChild = this->nextSbling;
    else
    {
        while(TravalPoint->nextSbling != nullptr)
        {
            if(TravalPoint->nextSbling == this)
            {
                TravalPoint->nextSbling = this->nextSbling;
                break; 
            }

            TravalPoint = TravalPoint->nextSbling;
        }
    }
    this->parent = this->nextSbling = nullptr;
}

TreeNode::TreeNode(const ElementType &element) : data(element)
{
    parent = FirstChild = nextSbling = nullptr;
}

LinkTree::LinkTree()
{
    root = new TreeNode("");
}

LinkTree::LinkTree(const ElementType &element)
{
    root = new TreeNode(element);
}

TreeNode *LinkTree::GetRoot()
{
    return root;
}

void LinkTree::show()
{
    root->show(root,-1);
}

LinkTree::~LinkTree()
{
    TreeNode::FreeNode(root);
}



void TreeNode::show(TreeNode *node,int depth)
{
    
    if(node == nullptr)
        return;
    //深度遍历
    for(int i = 0;i < depth ;i++)
        {
            std::cout<<" ";
        }
    if(node->parent != nullptr)
        std::cout<<node->data<<" "<<std::endl;
    show(node->FirstChild,depth+1);
    show(node->nextSbling,depth);
    
}

void TreeNode::FreeNode(TreeNode* node)
{
    if(node == nullptr)
        return;
    FreeNode(node->FirstChild);
    FreeNode(node->nextSbling);
    delete node;
}

int TreeNode::GetNodeHeight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    
    int Maxheight = 0 ;
    //找最高的子树
    TreeNode* TravelPoint = node->FirstChild;
    
    while(TravelPoint != nullptr)
    {
        int height = GetNodeHeight(TravelPoint);
        Maxheight = Maxheight > height ? Maxheight:height;
        TravelPoint = TravelPoint->nextSbling;
    }
    
    //自身高度  就等于 最高子树高度 + 1
    return Maxheight + 1 ;
}

TreeNode *TreeNode::GetParent()
{
    return this->parent;
}

std::string &TreeNode::GetData()
{
    return this->data;
}

void TreeNode::SetData(const ElementType &element)
{
    data = element;
}

TreeNode *TreeNode::FindNode(TreeNode *node,const ElementType& element)
{
    //终止条件
    if(node == nullptr)
        return nullptr;

    //排除根节点
    if(node->data == element  && node->parent != nullptr)
        return node;
    TreeNode* target = FindNode(node->FirstChild,element);
    if(target)
        return target;
    
    target = FindNode(node->nextSbling,element);
    if(target)
        return target;
    
    return nullptr;
}

void TreeNode::FindNode(TreeNode *node, const ElementType &element, DARRY::DynamicArray &a)
{
    //终止条件
    if(node == nullptr)
        return;

    //排除根节点
    if(node->data == element  && node->parent != nullptr)
    {
        a.InsertTail(node);
    }
    FindNode(node->FirstChild,element,a);

    
    FindNode(node->nextSbling,element,a);

}

DARRY::DynamicArray LinkTree::FindByElementType(const ElementType &element)
{
    DARRY::DynamicArray a;
    TreeNode::FindNode(root,element,a);
    return a;
}

int LinkTree::GetTreeHeight()
{
    return TreeNode::GetNodeHeight(root) - 1;//树根那一层，没算
    
}

std::string LinkTree::GetNodePath(TreeNode *node)
{

    if(node == nullptr)
        return std::string();
    
    std::string path = node->GetData();
   
    while (node->GetParent() != nullptr)
    {
        path = node->GetParent()->GetData() + "/" + path;
        node = node->GetParent();
     
    }
    return path;

}
